This invention relates to operation of routers in computer networks, and more particularly to maintenance of tables of Route Information Field information (RIF information) used in Source Routing Bridge subnets (SRB subnets).
A computer network comprises, in the simplest instance, a plurality of computers connected together by a communications media so that the computers can exchange messages. The computers are usually referred to as xe2x80x9cstationsxe2x80x9d.
In an exemplary embodiment, the communications media is arranged as a continuous ring and the stations are attached to the ring. This embodiment is referred to as a xe2x80x9ctoken ringxe2x80x9d local area network. The stations pass a special control message referred to as a xe2x80x9ctokenxe2x80x9d around the ring from one station to the next, and the station which holds the token transmits its messages onto the ring. When it is finished, the station transfers the token to the next station on the ring.
In an alternative exemplary embodiment, a local area network may implement the Ethernet protocol, or the closely related IEEE 802.3 Standard protocol. In an Ethernet system all terminals are connected to a common bus. Any station can transmit when it determines that the bus is free, and if a collision of packets is detected on the bus, then the stations quit transmitting and back off for a xe2x80x9cbackoff time intervalxe2x80x9d, and then try again. Other alternative network hardware technologies comprise FDDI token ring, ATM networks, etc.
The present discussion will focus particularly on token ring local area networks and their interconnection into larger networks.
A more complex token ring computer network comprises several token rings connected together by specialized stations referred to as xe2x80x9cbridgesxe2x80x9d. A message originating at a source station on one token ring can reach a destination station on another token ring by passing through one or more bridges, where the specialized job of the bridges is to forward messages from one token ring to another. In an exemplary embodiment, there may be a plurality of bridges between a first token ring and a second token ring. And the path which the message takes from a source station on a source token ring may pass through several intermediate token rings, before reaching the destination station on the destination token ring. Further, with a plurality of bridges between each pair of a plurality of token rings, there are many paths through token rings and bridges which the message can take from the source station and the destination station.
In an exemplary embodiment of computer networks, referred to as xe2x80x9csource route bridge (SRB) networksxe2x80x9d, the source station puts a specification of the path into the message. The specification is placed in the Route Information Field, the RIF, of the message. The RIF determines the path that the message is to follow through the bridges and token rings as it travels from the source station to the destination station. The RIF is placed by the source station into a header of the message. The bridges read the header and forward the message in accordance with the RIF specification.
A router is another specialized station which enables joining many computer networks together. For example, a router can join several computer networks formed from token rings and bridges. Also a router can join a token ring network to an Ethernet network, an FDDI network, etc., a telephone line or a telephone like line, etc. to form a Wide Area Network (WAN). The parts of a WAN may be widely separated, and joined by the telephone like line.
Routers are used to implement hierarchical addressing. Hierarchical addressing commonly uses a two level addressing method. A first level corresponds to Layer 2 of the OSI communications model, and a second level corresponds to Layer 3 of the OSI communications model. Hierarchical addressing permits Layer 3 to be independent of the communications media. The OSI model Layer 2 depends upon the communications media, the Layer 2 hardware technology (such as token ring, Ethernet, etc.), and other Layer 1 and Layer 2 details. Accordingly, a programmer can write code to implement Layer 3 functions without having concern for media dependent details which are handled by Layer 2 functions.
Hierarchical addressing is important in the construction of large networks, for example networks having many thousands of stations, by permitting a single computer to maintain a table of network addresses without having to keep a table giving the physical address of each individual computer on an entire network (for example, the Internet). A packet is sent to a router on the designated destination network, and that router keeps a table of the Layer 2 address of computers on the destination network. Without hierarchical addressing each router would have to keep tables of the Layer 2 addresses of all computers on the entire network, rather than simply keeping a network address referring to the computers on that particular network, and there are many fewer networks than there are computers. Radia Perlman treats hierarchical addressing in her book Interconnections, Bridges and Routers, published by Addison Wesley Publishing Company, in 1992, all disclosures of which are incorporated herein by reference, particularly in Chapter 6, pages 149-164.
Commonly used terminology refers to a small local area network as a xe2x80x9csubnetxe2x80x9d. For example, a plurality of token rings joined by bridges is a subnet. Also an Ethernet with one bus, or with several busses joined by bridges, is a subnet. A xe2x80x9cnetworkxe2x80x9d then refers to several subnets joined by a router. A router or a bridge can be connected to a telephone type line and join subnets in distant cities. For example, a bridge may forward frames using Data Link Switching to interconnect subnets in distant cities. A xe2x80x9cwide area networkxe2x80x9d (WAN) refers to subnets joined by routers or bridges, with the subnets typically being widely separated, for example, in different cities.
Each station has a physical address, also referred to as the MAC address, and the physical address is the OSI model Layer 2 address. The Layer 2 address is also referred to as the xe2x80x9cLink Addressxe2x80x9d. Also, each station is assigned a Layer 3 address or network address. For example, in the TCP/IP protocol the Layer 3 (network) address is referred to as the Internet Protocol address, or IP, address. The two levels of hierarchical addressing, the Layer 2 address and Layer 3 address, are typically used in the OSI model to implement subnets and networks.
The physical address is written into a semi-permanent memory device when the station is manufactured, and is referred to as the xe2x80x9cburned inxe2x80x9d address. However, the physical address may be changed by the owner of the station, by overriding the burned in address with a locally administered address, referred to as a LAA address.
On a subnet, a message is addressed to both the physical address and the Network address of the destination station. A bridge simply forwards the message. In the SRB network embodiment, where the message carries RIF information, the bridge obeys the instructions in the RIF of the message and forwards the message only along the path specified by the RIF.
However, when the source station and the destination station are on different subnets, the message is addressed to the physical address of a router and the Network address of the destination station. The addressed router is a station on the subnet of the source station. The router recognizes its physical address in the message, reads the Network address of the destination station from the header of the message, and then makes a decision as to how to route the message so that it goes to the destination station. The router writes a new header into the packet message before forwarding it onto the next SRB subnet The new header contains a new RIF. The new RIF directs the message through the token rings and bridges of the new SRB subnet. Alternatively, the new subnet may an Ethernet LAN, and in this case the router builds an Ethernet packet.
In making its decision, the router uses tables which correlate a physical address with a Network address. Also, for SRB subnets, the physical address is correlated with RIF information using a RIF table. The router must first, however, execute a protocol in order to populate its tables. Also, stations on the SRB subnet must know the physical address, the Network address, and the RIF information for a destination station. Thus each station must also go through protocols in order to populate its address tables.
There are a number of protocols used on computer networks for transferring messages from a source station, through intermediate bridges and routers, to a destination station. Names of various protocols comprise: TCP/IP, Apollo, Appletalk, CLNS, DECnet, IPX, Vines, XNS, SNA, and others. The TCP/IP protocol is often used to provide reliable message transport between Layer 3 entities. Under TCP/IP, commonly used protocols and messages for stations, including routers, to populate their tables include an Address Resolution Protocol (ARP) message; and, an All Routes Explorer (ARE) message. These two concepts, ARP and ARE messages, will be explained separately, although they are often combined in one packet, referred to as an xe2x80x9cARP Explorerxe2x80x9d packet. Protocols other than TCP/IP will be discussed hereinbelow.
An ARP message is used by a first station to learn the physical address needed to reach a second station where the fists station already knows the Network address of the second station. Often, a source station will know the Network address of an intended destination station, but will not know the physical address needed to reach the destination station. Also, the source station will not know, and does not need to know, the media over which a packet must travel to reach the intended destination station.
In the event that both the first and second stations are on the same subnet, the needed physical address will be the physical address of the second station. However, in the event that the first and second stations are on different subnets, the necessary physical address will be the physical address of a router. Both the subnet of the first station and the remote second station may be the same type of media, for example SRB subnets, or for a further example both may be on Ethernets. Alternatively one subnet may be an SRB subnet and the other a different media technology, for example Ethernet. Once the first station learns both the Network address and the physical address to place in a message, it caches this information in a table referred to as the xe2x80x9cARP tablexe2x80x9d. Protocols other than TCP/IP use xe2x80x9cARP likexe2x80x9d tables to provide a binding between a station""s physical address and network address.
The example in which both the source subnet and the destination subnet are SRB subnets, is next described. Once the source station learns the proper physical address to reach the second station, the source station uses ARE messages in order to learn a route. The source station places the Network address and physical address in the ARE message. The ARE message traverses all routes from the source station to the second station whose physical address is written into the message (either the intended destination station or the physical address of a router).
In a commonly used embodiment one packet, the xe2x80x9cARP Explorer packetxe2x80x9d, is used with the ARP functionality in Layer 3 fields of the packet, and the ARE functionality in the Layer 2 fields, as described in more detail hereinbelow. The ARP Explorer packet is referred to as a xe2x80x9cpacketxe2x80x9d because it is a message between Layer 3 functions in a source station and in a destination station.
Both the ARP message and the ARE message are forwarded by bridges. However, both the ARP message and the ARE message are confined to the subnet of their source station, and are not routed by a router. Also, the ARP Explorer packet is forwarded by bridges but is not routed by routers, and so is confined to the subnet of its source station.
The ARE message protocol gives a source station the route to use to reach the station whose physical address (router or destination station) is needed to reach the destination station. The route information is then stored in the station in a RIF table. The RIF information must be updated frequently, as bridges may become congested, bridges may fail, telephone lines may be cut, etc.
Hereinafter the TCP/IP terminology will be used, and the Network address will be referred to as the IP address. When the ARP and ARE protocols are combined in one packet, referred to as an ARP Explorer packet, then Layer 3 in the packet controls the ARP functionality and Layer 2 controls the ARE functionality. The ARP Explorer packet is transmitted onto a SRB subnet by a source station, and the source station may be either a router or an end station. The ARP Explorer packet is confined to the SRB subnet as it is not routed by a router. The ARP Explorer packet is forwarded by all of the bridges in the SRB subnet because of the ARE functionality. A route is built up in the RIF field of the ARP Explorer packet as it is forwarded by various bridges onto various token rings. The ARP Explorer packet is examined by all end stations receiving it by a Layer 3 function to determine if the IP address in the ARP inquiry field matches the receiving station""s IP address. In the event that the receiving station finds a match between the IP address in the ARP inquiry field of the ARP Explorer packet and the receiving station""s IP address, the receiving station transmits a response packet to the source station. The response packet is directed back to the source station along the route built up in the RIF field of the ARP Explorer packet, but in reverse order.
Build up of the route in the RIF field of the ARP Explorer packet is next discussed in greater detail. The ARE function in the ARP Explorer packet has the property that when it reaches a bridge on a first token ring, a copy of the ARP Explorer packet is both forwarded by the bridge to the next token ring, and a copy continues around the first token ring. As it is forwarded by a bridge, the ring number of the ring it is going to, along with the bridge number of the forwarding bridge, is written into the RIF of the ARP Explorer packet. The RIF information is built up on a xe2x80x9cbridge by bridgexe2x80x9d basis as pairs of ring number and bridge number, as the ARP Explorer packet is forwarded throughout the subnet. Further, if the copy of the ARP Explorer packet continuing around the first token ring is received by a second bridge, again a copy is forwarded by the bridge to a token ring (either another token ring or the same xe2x80x9cnextxe2x80x9d token ring if more than one bridge joins the first token ring and the xe2x80x9cnextxe2x80x9d token ring), and also a copy continues around the first token ring. As a result, the destination station receives a plurality of copies of the ARP Explorer packet. And each copy specifies, in the RIF of the ARP Explorer packet, the path taken by that copy through the subnet.
Upon receipt of each copy of the ARP Explorer packet, the destination station having the IP address which is in the IP inquiry field of the ARP Explorer packet then resets a xe2x80x9cdirection bitxe2x80x9d in the ARP Explorer packet and re-transmits it onto the subnet as an xe2x80x9cARP Explorer responsexe2x80x9d message. The xe2x80x9cdirection bitxe2x80x9d is an indicator in the header of the message which specifies whether the path of the RIF is to be traversed from left to right, which takes the message from the source station to the destination station, or from right to left which takes the ARP Explorer response message back to the source station. Each copy of the ARP Explorer packet received by the destination station is thereby converted into an ARP Explorer response message which is received by the source station. Each ARP Explorer response message received by the source station specifies a different path through the subnet to the destination station. The source station then chooses one of the routes to populate its RIF table. One method of choosing the route from the duplicates is to choose the route in the RIF field of the first received ARP Explorer response packet. The source station then uses the RIF value until an event occurs requiring updating of the RIF table: for example, the expiration of a time interval and the transmission of another ARP Explorer packet; or for example, when the source station is a router, the receipt of a packet to be routed to that destination station.
Traditionally, a router may update its ARP table and RIF table upon receipt of an ARP Explorer packet transmitted by an end station. Upon receipt of the ARP Explorer packet, the router transmits an ARP Explorer response message to the end station, just like any other station. Also, the router reads the RIF information from the ARP Explorer packet and uses it to update its ARP table and RIF table entries.
Another commonly used technique for updating RIF information is for a station to listen to message traffic, and to copy RIF information, physical address, and IP address combinations from all messages, and use this information to simply overwrite older entries in its ARP table and its RIF table. Particularly, some routers have been designed to listen to message traffic, and to use REF information, physical address, and IP address combinations read from every message which the router routes, in order to update the entry in the router""s ARP table and RIF table. Update is accomplished by overwriting the current entry in the table.
In the event that a router receives a message having the physical address of the router and the IP address of a station which is not on the subnet from which the message arrives, then the router makes decisions. First the router checks its ARP table to learn if the IP address is in its ARP table by using the IP address as an index into the ARP table. If the IP address is indeed in the ARP table, the router now knows the proper subnet to route the message to, and knows the proper physical address to put in the message (the proper physical address may again be either the destination station or another router). Next, the router checks its RIF table, by using the Layer 2 address as an index into the table, in order to determine if the physical address is in the RIF table, and if it is, the router simply writes the RIF information into the RIF of the message and routes the message on its way. However, in the event that the needed information is not in either the ARP table or the RIF table, the router must transmit an ARP Explorer packet in order to build an entry in its ARP and RIF tables.
In the related patent application mentioned above, a new and novel table which extends the physical address to include the RIF information for use in a router is disclosed. This extension of the physical address permits the ARP table to keep both the correlation between the physical address and the IP address, as well as the RIF information needed by the router to route a message to the destination station. With this new extended ARP table the problem of receipt of multiple copies of the ARP Explorer response packet remains.
There is needed a mechanism whereby a router can update its RIF entry for a destination station on a token ring network using the new combined ARP and RIF table, use a protocol which gives a xe2x80x9cbestxe2x80x9d route (for example a fastest route), and update the RIF entry on a timely basis.
A router transmits an ARP Explorer request packet onto a subnetwork in order to learn the route (RIF information) from the router to a destination end station. The end station receives a plurality of ARP Explorer request packets from the router because of multiple paths in an SRB network, and the end station transmits an ARP Explorer response packet in response to each ARP Explorer request packet received. The invention adopts the path of the first ARP Explorer response packet received by the router from the end station for the RIF information from the router to the end station, and uses a xe2x80x9cduplicate ignorexe2x80x9d timer in order to avoid freezing this route into the router tables. The timer begins running upon receipt of the first ARP Explorer response packet, and expires after an xe2x80x9cupdate time intervalxe2x80x9d. No further ARP Explorer response packet is processed until after expiration of the update time interval. All duplicate ARP Explorer response packets are expected to arrive during the update time interval. Therefore the routing information is not updated by a second ARP Explorer response packet until after all duplicate ARP Explorer response packets have been received and rejected. Use of the update time interval chooses the fastest path, as the first ARP Explorer response packet to be received by the router is probably generated by the first ARP Explorer request packet received by the intended destination end station, and probably traveled along the fastest path from the router to the intended destination end station. Expiration of the duplicate ignore timer allows later issued ARP Explorer request packets to dynamically update the RIF information as conditions on the network change, after expiration of the duplicate ignore timer. The RIF information will be updated after the router executes a subsequent ARP Explorer request protocol, and receives the first of the duplicate ARP Explorer response packets, with the duplicate ignore timer permitting only the first received ARP Explorer response packet to update the RIF information in the router.
A router receives an ARP Explorer request packet transmitted onto a subnetwork by an end station. The router receives a plurality of ARP Explorer request packets from the end station because of multiple paths in an SRB network. The invention adopts the path of the first ARP Explorer request packet received by the router from the end station for the RIF information from the router to the end station, and uses a xe2x80x9cduplicate ignorexe2x80x9d timer in order to avoid freezing this route into the router tables